1. Field of the Invention
The present invention relates generally to techniques for dynamically reconfiguring finite but relocatable resources in a distributed computer system, and specifically, to a system and method for caching and replicating multimedia content such as objects on multimedia servers distributed throughout the Internet.
2. Discussion of the Prior Art
FIG. 1 illustrates a typical distributed computer system consisting of a plurality of clients (110, 111, 112), a plurality of servers (120, 121, 122), and several independent collections of objects (130, 131, 132). These components are connected by a computer networked environment (160) that enables a client (e.g., 111) to directly place a request message (140) for one or more objects from a server. The system allows such server (e.g., 121) to establish a streaming connection (150) for delivering an object to the requesting client (e.g., 111). This environment is typical of the Internet where a browser represents the client, a web server represents the server, a web site represents the collection of objects, the Internet represents the computer-networked environment. As known, the HTTP protocol provides the ability for a client to request an object from a given server via a location bound identifier referred to as a Universal Resource Locator (URL). The Transmission control Protocol (TCP) provides the ability to stream an object (such as a web page or a video file) from the web server to the client.
FIG. 2 depicts in further detail the components of a server (e.g., 120) as found in the environment depicted in FIG. 1. The server contains a finite amount of local resources (200) comprised of memory (210), CPU (220), disk storage (230), and, network bandwidth (240). The server is associated with a collection of objects (130). In this particular case, the collection is composed of four objects (281, 282, 283, 284). Interactivity with a client such as VCR interactivity during playback (e.g., pause, rewind, stop, fast forward, etc.,), billing, security, etc. are handled by the server""s service logic component (250). A signaling protocol (261) (e.g., HTTP) allows the server to receive requests (e.g., 140) from clients. For a client (e.g., 111) to access an object (e.g., 281) on the server""s collections, the server allocates a portion of its resources (200) to the corresponding streaming connection (150). Because resources are finite, a local admission control process (260) is used to determine whether an incoming request can be served. A local resource management process (270) is used to reserve, access, monitor, and de-allocate local resources (200) in the server (for example, disk storage (HDD), bandwidth (B), CPU cycles (CPU), memory (MeM), etc. such as depicted in FIG. 2). The network streaming process (275) relies on a streaming protocol (271) to deliver content to its clients by establishing and managing streaming connections (e.g., 150) to clients. Management of resources at any particular server (e.g., 120) is completely independent from management of resources at any other particular server (e.g., 121). Furthermore, collections (e.g., 130 and 131) at different servers are independent from each other. In particular, though copies (281, 285) of the same object, e.g., object xe2x80x9cO4xe2x80x9d may exist on two different collections (130, 131) at different servers (120, 121) there exists no means of relating these copies (281, 285) to each other.
As depicted in FIG. 3, the distributed computer system 10 (of FIG. 1) may employ an object directory service 300 embodied as an object request broker (ORB) which provides the directory service over a collection of object sites (e.g., 130, 131, 132), and, extends location transparency to clients (e.g., 110, 111, 112) requesting objects (e.g., a media content file 04) from the distributed object collection (130, 131, 132). An object directory service (300) provides information necessary to locate any object throughout the computer-networked environment (160). The directory (310) employed particularly tracks the server associated with an object. For example, the first directory entry illustrates that object 281 is found on server 120 whereas the second directory entry illustrates that object 285 is found on server 121.
The task of leveraging the increased availability of widely distributed content and resources becomes very important with the proliferation of the next generation of the Internet, e.g., Internet2. The emerging Internet projects address the creation of a leading edge network for a new generation of applications that fully exploit the capabilities of broadband networks. Very high bandwidth and bandwidth reservation will allow materials such as continuous digital video and audio to move from research use to much broader use and include images, audio, and video in a way currently not possible. In such a widely distributed environment, accountable, efficient, and self-regulated management of resources will be desirable and most importantly, necessary.
The driving force behind the movement of Internet to the next generation is the commercialization of rich multimedia content. Digital library collections produced by corporations, entertainment material created by movie studios, and interactive instructional presentations developed by universities are soon to be available over the Internet, thus creating a new and broad source of revenue.
The emerging Internet relies on the bandwidth, which is on the order of several magnitudes larger than current Internet provides. It also alleviates network resource management and QoS control by introducing correspondent reservation and monitoring mechanisms. However, it is clear, that to date, mechanisms for the collective management of multiple media connections that efficiently leverage the sharing of resources across multiple servers in a wide area network are not found.
There is envisioned three major conditions for successful commercialization of those newly arising applications: first, mechanisms need be provided to allow paying users to establish a contract with service providers to reserve required infrastructure components and resources at a mutually agreed price for which providers establish and support a guaranteed quality of service; second, the resources supply would have to be sufficient to meet random changes of the demand, which may be completely unpredictable during architectural studies; and, third, service providers should safely rely on the system for effective security, rights and royalties management, accounting and billing for the consumption of dynamically re-configurable distributed virtual resources.
The current focus of resource management in the today""s Internet, if any, relates to the setup and management of individual and independent media connections to server resources. However, the danger of this approach becomes clear when the presentations reuse multiple primary sources of content. To enforce the necessary quality as well as to control the usage and distribution when reusing multiple sources of content, two approaches are possible. One approach is to copy all content onto a single server (or a cluster of servers) during authoring, and replicating, as necessary, the final result to as many servers according to predicted demand. Primary content providers would then establish copyright charges, based on a-priori market analysis. On the positive side, the control of distribution, security, and billing functions become much easier, than in case of distributed content. On the negative, if the demand is estimated incorrectly, the profit is not maximized for either primary or secondary (i.e., reuse) content providers. Finally, the most dangerous problem is that this approach leads to over-engineering of resources while it does not prevent dropout of excessive requests. Such an approach is typical for today""s Internet, because current multimedia content is generally not memory hungry, as compared with emerging multimedia applications.
Another approach would be to reassemble content on a need basis, for both authoring and dissemination. It would allow content to be stored once, but used as many times as necessary, establish charges proportionally to content and resources usage, and alleviate storage demand. However, it requires a system to dynamically manage multiple and frequently heterogeneous resources. In addition, this approach exacerbates security, and resource engineering. A demand for the particular segment can not be predicted at all, because this segment may be used in completely different, even orthogonal applications. Now, if the demand for a single segment can not be met, multiple applications are affected. The latter approach, however, is the only sensible way to be used by future Internet, because from the resource point of view, it is the most economical, and serving a maximum number of users.
Thus, it would be highly desirable to provide a system and method that allows all three major commercialization conditions to be satisfied.
There are a number of publications and patents in the area of QoS-driven resource management. Most of the work has been focused on either the network, as described in U.S. Pat. No. 5,388,097 issued Feb. 7, 1995 to Baugher, M. J. et al., and entitled xe2x80x9cSystem and Method for Bandwidth Reservation for Multimedia Traffic in Communication Networks,xe2x80x9d and U.S. Pat. No. 5,581,703 issued Dec. 3, 1996 to Baugher, M. J. et al, and entitled xe2x80x9cMethod and Apparatus for Reserving System Resources to assure Quality of Servicexe2x80x9d; or, the operating system, such as described in the reference xe2x80x9cAn Architecture Towards Efficient OS Support for Distributed Multimediaxe2x80x9d, Proceedings of ISandT/SPIE Multimedia Computing and Networking Conference ""96, San Jose, Calif., January 1996 by David K. Y. Yau and Simon S. Lam. With the proliferation of multimedia services on Internet, it was soon realized that while IP networks were able to provide a simple, best-effort delivery service, the IP protocol is not suited for use with new real-time applications, such as multimedia streaming, Virtual Reality applications, distributed supercomputing. As a result, new network protocols, such as Resource Reservation Setup Protocol (RSVP) (See, e.g., xe2x80x9cThe Grid: Blueprint for a New Computing Infrastructure,xe2x80x9d Edited by Ian Foster and Carl Kesselman, Chapter 19, pp. 379-503, Morgan Kauffman Publishers, 1999); Real Time Transport Protocol (RTP); Real Time Transport Control Protocol (RTCP) and others, were developed (See, e.g., William Stallings, xe2x80x9cHigh-Speed Networks: TCP/IP and ATM Design Principlesxe2x80x9d, Prentice Hall, 1997; and, I. Busse, B. Deffner, and H. Schulzrinne, xe2x80x9cDynamic QoS Control of Multimedia Applications based on RTPxe2x80x9d, Computer Communications, January 1996), enabling applications to request and negotiate network QoS parameters, such as bandwidth and latency. Deployment of those protocols on the current Internet has not been successful, firstly because it required upgrading all the non-RSVP routers and servers system software. Secondly, even if RSVP were deployed on the current Internet, very limited bandwidth and computing resources would still have been the bottleneck for successful deployment of real-time applications. The current Internet was built on the backbone, enabling cross-country communications on relatively unclogged T3 (45 megabit per second). Proliferation of graphic pages, and streaming audio and video applications depleted those resources quite fast. Even worse, the rate of user""s population growth is considerably higher than newly build network resources.
The National Science Foundation and MCI Corporation, responding to the emerging needs of Internet community has been building a new network, called vBNS (very-high-performance Backbone Network Service). This nationwide network also provides a backbone for the two foundations, university-led effort called Internet 2 and by federal research agencies, called New Generation Internet. The vBNS allows most of the connected institutions to run at 622 million bits per second (OC12). By the year 2000, vBNS is expected to operate at 2.4 gigabits per second (2,400 megabits per second) by the year 2000.
The vBNS system exploits RSVP protocol to support two distinct classes of services: a Reserved Bandwidth Service, i.e. a service with bandwidth commitment, and a traditional best-effort IP service (See, e.g., Chuck Song, Laura Cunningham and Rick Wilder, xe2x80x9cQuality of Service Development in the vBNSxe2x80x9d, MCI Communications Corporation, provided at the URL http://www.vbns.net/presentations/papers/QoSDev/ieeeqos.htm. Still, resource management at the network layer for vBNS is done separately from operating system layer and in isolation from application needs and availability of the end-resources, such as storage and computing resources.
A new breed of high performance applications such as remote surgery, robotics, tele-instrumentation, automated crisis response, digital libraries of satellite data, distance learning via multimedia supported Web sites, enhanced audio, and video, is emerging. However, to accommodate such high performance applications and their continuous media flows, it is not enough to increase or reserve network capacity. These new applications require end-to-end resource reservation and admission control, followed by co-ordination of distributed functions such as: (a) resource scheduling (e.g., CPU, disk, etc.) at the end-system(s), (b) packet scheduling and flow control in the network, and (c) monitoring of the delivered end-to-end quality of service. It is essential that quality of service is configurable, predictable and maintainable system-wide, including the end-system devices, communications subsystem, and networks. Furthermore, all end-to-end elements of distributed systems architecture must work in unison to achieve the desired application level behavior.
Up do date, there has been considerable effort in the development of end-to-end quality of service support. Among them are Heidelberg QoS Model, developed within HeiProject at IBM""s European Networking Center and described in the reference entitled xe2x80x9cHeiRATxe2x80x94Quality of Service Management for Distributed Multimedia Systemsxe2x80x9d, Multimedia Systems Journal, 1996 by Volg, C., Wolf, L., Herrtwich, R. And H. Wittig; an Extended Integrated Reference Model (XRM), developed by COMET group at Columbia University such as described in the reference entitled xe2x80x9cBuilding Open Programmable Multimedia Networksxe2x80x9d, Computer Communications Journal, Vol. 21, No. 8, pp. 758-770, June 1998 by Campbell, A. T., Lazar, A. A., Schulzinne, H. And R. Stadler; OMEGA end-point architecture, developed as the interdisciplinary research effort in the University of Pennsylvania such as described in the reference entitled xe2x80x9cDesign, Implementation and Experiences of the OMEGA End-Point Architecturexe2x80x9d, Technical Report (MS-CIS-95-22), University of Pennsylvania, May 1995 by Nahrstedt K. And J. Smith; in-serv Architecture which is a contribution of the Internet Engineering Task Force (IETF) such as described in the reference entitled xe2x80x9cA Framework for End-to-End QoS Combining RSVP/Intserv and Differentiated Services,xe2x80x9d Internet Draft, IETF, March 1998 by Bernet Y, et al.; the Quality of Service Architecture QoS-A, developed by A. Campbell, and presenting an integrated framework dealing with end-to-end QoS requirements such as described in the reference entitled xe2x80x9cA Quality of Service Architecturexe2x80x9d, PhD thesis, Lancaster University, January 1996 by Andrew T Campbell. Another reference which analyzes the above mentioned QoS paper is entitled xe2x80x9cA Survey of QoS Architecturesxe2x80x9d, ACM/Springer Verlag, Multimedia Systems Journal, Special Issue on QoS Architecture, Vol. 6, No. 3, pp. 138-151, May 1998 by Aurrecoechea, C., Campbell, A. T. and L. Hauw.
Substantial work has been done by SRI International, developing an End-to-End Resource Management of Distributed Systems (ERDoS), which enables adaptive, end-to-end, scalable resource management of distributed systems such as described in the reference ERDOS QoS Architecture, Technical Report, SRI International, May 1998. An extensible Resource Specification Language (RSL) and the resource management architecture has been implemented within Globus meta-computing toolkit, and used to implement a variety of different resource management strategies such as described in Czajkowski, K., et al., xe2x80x9cA Resource Management Architecture for Metacomputing Systemsxe2x80x9d Proc. IPPS/SPDP ""98 Workshop on Job Scheduling Strategies for Parallel Processing, 1998; and Foster, I., Kesselman, C., xe2x80x9cThe Globus Product: A Status Reportxe2x80x9d Proc. IPPS/SPDP ""98 Heterogeneous Computing Workshop, pp. 4-18, 1998.
While the architectures described in the above-mentioned references are directed resource reservation and management of end-to-end resources, they generally assume a single, even geographically limited network subsystem which provides bounds on delay, errors and meet bandwidth demands, and an operating system which is capable of providing run time QoS guarantees. However, the next generation Internet must be viewed not as only a network of networks, but first and foremost a system of distributed systems. In this paradigm, not only the communication resources, but also the computing and storage servers are shared among many users.
Thus, the architectures mentioned above do not provide a coordinated management of overall system resources as a function of request activities for individual content and computing resources. It deals with resources pre-assigned to particular services. Consequently, quality of service must be degraded in response to growing volume of requests for such services over and above an established limit. As the above-mentioned architectures focus on providing QoS as requested by application, they do not take an advantage of a possible aggregation of resources due to commonality between user requests for a particular service.
For example, it would be desirable to determine commonality for the usage history of a particular multimedia content, e.g., bursts of requests within short time intervals, the proximity of origination addresses of requests, etc. In addition, the architectures described above do not allow for dynamic monitoring and recording of resource consumption for individual services as well as for groups of related services, with the purpose of calculating cost of service for individual clients.
Thus, it would be highly desirable to provide a mechanism capable of providing an adaptive resource management function for distributed resources that could, on-demand, shape system capacity to the needs of the environment where such mechanism is suited for the next generation of the Internet.
It is an object of the invention to provide a system and method for managing and controlling the distribution, sharing and pooling of resources in an Internet/World Wide Web environment, and for managing the placement of objects onto servers according to a set criteria such as predicted aggregated demand for objects.
The present invention resolves the above problems by introducing an intermediary control node (herein referred to as the controller) between clients and servers that provides mechanisms capable of modifying available capacity on servers in terms of the placement and number of objects made available on these servers in accordance to some set criteria. In particular, the present invention comprises a capacity shaping mechanism for matching predicted aggregated demand for objects to available capacity. To this end, predicted demand statistics are generated by analyzing the aggregated request stream presented to the intermediary control node whereas available capacity is loosely estimated by a special protocol between servers and the controller node.
More particularly, the present invention introduces the notion of a global server which provides a spare, shared, and highly available capacity that can be used to assist a multimedia server by temporarily increasing the overall system capacity associated with some particular multimedia object to match its predicted demand. The present invention additionally introduces the notion of a transient replica which replica acts as a migrating object of limited lifetime that responds to demand and capacity conditions. To do so, the controller node monitors demand and capacity and uses, creates, and deletes transient replicas from global servers. These complementary notions are used to provide a system and method to dynamically control the placement and number of replicas on an Internet/web environment. It should be noted that the creation of a transient replica does not reserve resources at a global server. Instead, on-demand replication is rather used as a tool to increase the likelihood of finding an available replica during the processing of subsequent requests for the same object. For this reason, the present invention is particularly suited for virtual proximity of computational and storage resources on the next generation of the Internet.
Advantageously, the system of the invention achieves capacity shaping for matching predicted aggregated demand for objects to available capacity while preserving the autonomy of servers over the control of their resources. That is, the resource management system is decentralized in that resource management controls (e.g., admission control, resource reservation, resource measurements, resource scheduling, etc.,) are implemented locally, at each server, and not centralized at the controller. Controllers do not directly manage servers and their resources. Instead, controllers represent agents that forward capacity shaping control recommendations to servers. This is achieved without imposing stringent monitoring requirements on the controller about the state of resources and servers on the system. Signaling protocols between servers and controller allow controllers to maintain resource management state during run-time in a fault tolerant way. The system tradeoffs signaling overhead against state maintenance overhead.